'''
https://leetcode.cn/problems/binary-search-tree-iterator/?envType=study-plan-v2&envId=top-interview-150
'''

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = stack = []
        while root:
            stack.append(root)
            root = root.left

    def next(self) -> int:
        stack = self.stack
        cur = stack.pop()
        res = cur.val
        cur = cur.right
        while cur:
            stack.append(cur)
            cur = cur.left
        return res

    def hasNext(self) -> bool:
        return len(self.stack) > 0


# 暴力
class BSTIterator2:
    def __init__(self, root: TreeNode):
        self.elements = elements = []
        def f(root):
            if root:
                f(root.left)
                elements.append(root.val)
                f(root.right)
        f(root)
        self.idx = 0
        self.n = len(elements)

    def next(self) -> int:
        self.idx += 1
        return self.elements[self.idx - 1]

    def hasNext(self) -> bool:
        return self.idx < self.n

